package com.tree.leetcode.linklist;

import com.tree.leetcode.common.ListNode;

import java.util.*;

import static com.tree.leetcode.common.ListNode.*;

/**
 * package com.tree.leecode
 * description:
 * 反转一个单链表。
 * <p>
 * * Definition for singly-linked list.
 * * public class ListNode {
 * *     int val;
 * *     ListNode next;
 * *     ListNode(int x) { val = x; }
 * * }
 * 示例:
 * <p>
 * 输入: 1->2->3->4->5->NULL
 * 输出: 5->4->3->2->1->NULL
 * 进阶:
 * 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/reverse-linked-list
 *
 * @author tree
 * @date 2020-03-04 09:35
 */


public class ReverseList_216 {
    public static void main(String[] args) {
        ListNode node = nodeBuilder();
        System.out.println("反转前：");
        printNodeResult(node);

        System.out.println("反转后：");
        ListNode node2 = reverseListByStack(node);
        printNodeResult(node2);


    }

    /**
     * 方法一：迭代
     * 假设存在链表 1 → 2 → 3 → Ø，我们想要把它改成 Ø ← 1 ← 2 ← 3。
     *
     * 在遍历列表时，将当前节点的 next 指针改为指向前一个元素。由于节点没有引用其上一个节点，因此必须事先存储其前一个元素。在更改引用之前，还需要另一个指针来存储下一个节点。不要忘记在最后返回新的头引用！
     *
     * 作者：LeetCode
     * 链接：https://leetcode-cn.com/problems/reverse-linked-list/solution/fan-zhuan-lian-biao-by-leetcode/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     * @param head
     * @return
     */
    public static ListNode reverseList2(ListNode head) {
        if(head == null ) {
            return null;
        }
        ListNode pre = null;
        ListNode curr = head;
        while (curr!=null){
            ListNode tmp = curr.next;
            curr.next = pre;
            pre = curr;
            curr = tmp;
        }
        return pre;
    }

    /**
     * 使用栈stack
     * @param head
     * @return
     */
    public static ListNode reverseListByStack(ListNode head) {
//        Stack<Integer> stack = new Stack();
//
//        ListNode node = head;
//        while (node != null) {
//            stack.push(node.val);
//            node = node.next;
//        }
//        if (stack.isEmpty()) {
//            return null;
//        }
//        ListNode node2 = new ListNode(stack.pop());
//        while (!stack.isEmpty()) {
//            addNode(node2, stack.pop());
//        }
//        return node2;

        if(head == null) {
            return null;
        }

        Stack<Integer> s = new Stack();
        ListNode current = head;
        while(current != null ){
            s.push(current.val);
            current = current.next;
        }

        ListNode reverseNode = new ListNode(s.pop());
        while(!s.isEmpty()){
            int v = s.pop();
            addNode(reverseNode,v);
        }
        return reverseNode;
    }
}
